package com.caoyanan.algorithm.question.zuoTraining.training004.class01;

import com.caoyanan.algorithm.question.zuoTraining.struct.TrieNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * 给定一个字符类型的二维数组board，和一个字符串组成的列表words。
 * 可以从board任何位置出发，每一步可以走向上、下、左、右，四个方向，
 * 但是一条路径已经走过的位置，不能重复走。
 * 返回words哪些单词可以被走出来。
 * 例子
 * board = [
 *   ['o','a','a','n'],
 *   ['e','t','a','e'],
 *   ['i','h','k','r'],
 *   ['i','f','l','v']
 * ]
 * words = ["oath","pea","eat","rain"]
 * 输出：["eat","oath"]
 *
 * @author: caoyanan
 * @time: 2021/6/4 11:43 上午
 */
public class Question06_MatrixWordPath {

    public static void main(String[] args) {
        char[][] arr = new char[][]{new char[]{'o', 'a', 'a', 'n'}, new char[]{'e', 't', 'a', 'e'},
                new char[]{'i', 'h', 'k', 'r'}, new char[]{'i', 'f', 'l', 'v'}};
        String[] words = new String[]{"oath", "pea", "eat", "rain"};
        String[] result = wordSearch(arr, words);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 可以从任意位置出发，看能走出哪些单词
     * 首先遍历每一个位置，从 i,j位置出发，看是否能走过 words 中的每个单词
     * 因为是一个一个从左往右判断每个单次的字符，所以可以应用一个前缀树 trie树
     *
     * 减枝，输入字符串可能重复，
     * 路径中有多条str[i]路径,用pass减减，但是pass必须是真的有一条路径存在才能减，只能走一半的不能减，所以递归需要返回走通了多少个单词
     * @param arr
     * @param words
     * @return
     */
    private static String[] wordSearch(char[][] arr, String[] words) {

        TrieNode head = new TrieNode();
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            if (set.contains(words[i])) {
                continue;
            }
            set.add(words[i]);
            fillInTrieTree(head, words[i]);
        }

        List<String> answer = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                process(arr, i, j, head, answer, "");
            }
        }

        return answer.toArray(new String[]{});
    }

    /**
     * 递归含义： arr为矩阵，i行j列，next是要搜索的字符trie树，answer收集答案, path为已经走过的节点
     * 即，准备登上矩阵的i，j位置(还没登上去)，搜索trie树上的字符串(trie树来判断能不能登上去arr[i][j])位置，
     * 将搜索到的答案放到answer数组中,同时，将路径记录到path中
     * @param arr
     * @param i
     * @param j
     * @param next
     * @param answer
     */
    private static int process(char[][] arr, int i, int j, TrieNode next, List<String> answer, String path) {

        // 当前节点已经走过或者已经越界了
        if (i < 0 || i >= arr.length || j < 0 || j >= arr[i].length || arr[i][j] == 0) {
            return 0;
        }
        char currentChar = arr[i][j];
        int index = arr[i][j] - 'a';
        next = next.nexts[index];
        // 没有路可以走
        if (next == null || next.pass == 0) {
            return 0;
        };
        String currentPath = path + arr[i][j];
        // 如果当前节点就是一个单词的结束
        if (next.end > 0) {
            answer.add(currentPath);
            next.end --;
        }
        // 当前节点走过一次，接着往上下左右走
        arr[i][j] = 0;

        // 从当前节点走通了多少个单次
        int fix = 0;
        fix += process(arr, i + 1, j, next, answer, currentPath);
        fix += process(arr, i -1, j, next, answer, currentPath);
        fix += process(arr, i , j + 1, next, answer, currentPath);
        fix += process(arr, i , j -1 , next, answer, currentPath);

        next.pass-= fix;

        // 恢复现场
        arr[i][j] = currentChar;
        return fix;

    }

    private static void fillInTrieTree(TrieNode head, String word) {
        head.pass++;
        char[] chars = word.toCharArray();

        TrieNode node = head;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (node.nexts[index] == null) {
                node.nexts[index] = new TrieNode();
            }
            node = node.nexts[index];
            node.pass++;
        }
        node.end++;
    }
}
